⟸ Go Back ⟸

Exercise 1 (Homework 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE)

Classification I: basic properties of TMs

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid M_{p}(p)=p\}
2. \{p \mid \exists y\ M_{y}(p)=p\}
3. \{\langle p,z\rangle \mid \exists y\ M_{p}(y)=z\}
4. \{\langle p,z\rangle \mid \exists y\ M_{p}(y)\neq z\}
5. \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\uparrow \text{ if and only if } M_q(z)\!\uparrow)\}
6. \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\downarrow \text{ if and only if } M_q(z)\!\uparrow)\}